﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Space_Conquest
{

    class PathNode
    {

        #region Private Members

        PathNode _parent;
        UnitDirection _directionSpawnedFrom;
        MapPoint _point;
        List<PathNode> _children = new List<PathNode>();

        #endregion

        #region Properties

        public PathNode Parent
        {
            get
            {
                return _parent;
            }
        }

        public PathNode this[int index]
        {
            get
            {
                return _children[index];
            }
        }

        public List<PathNode> Children
        {
            get
            {
                return _children;
            }
        }

        public int ChildrenCount
        {
            get
            {
                return _children.Count;
            }
        }

        public MapPoint MapPoint
        {
            get
            {
                return _point;
            }
        }

        #endregion

        #region Constructors

        public PathNode(PathNode parent, MapPoint point, UnitDirection directionSpawnedFrom)
        {

            _parent = parent;
            _point = point;
            _directionSpawnedFrom = directionSpawnedFrom;

        }

        #endregion

        #region Methods

        public void AddChild(PathNode child)
        {

            _children.Add(child);

        }

        public PathNode SpawnChild(UnitDirection direction)
        {

            // Temporary references
            PathNode newNode = null;
            MapPoint newPoint = null;
            UnitDirection spawnDirection = UnitDirection.Left;

            // Determine new point and,
            // Get opposite direction so new node knows where it was spawned from                
            switch(direction)
            {

                case UnitDirection.Down:
                    newPoint = new MapPoint(_point.X, _point.Y + 1);
                    spawnDirection = UnitDirection.Up;
                    break;
                case UnitDirection.Up:
                    newPoint = new MapPoint(_point.X, _point.Y - 1);
                    spawnDirection = UnitDirection.Down;
                    break;
                case UnitDirection.Right:
                    newPoint = new MapPoint(_point.X + 1, _point.Y);
                    spawnDirection = UnitDirection.Left;
                    break;
                case UnitDirection.Left:
                    newPoint = new MapPoint(_point.X - 1, _point.Y);
                    spawnDirection = UnitDirection.Right;
                    break;
                default:
                    throw new Exception("Error Spawning child, unknown direction");

            }

            // Create new node
            newNode = new PathNode(this, newPoint, spawnDirection);
            _children.Add(newNode);

            return newNode;

        }

        public List<UnitDirection> GetDirectionListFromEndingNode()
        {

            List<UnitDirection> tempList = new List<UnitDirection>();
            PathNode currentNode = this;

            while (currentNode.Parent != null)
            {
                tempList.Insert(0, GetOppositeDirection(currentNode._directionSpawnedFrom));
                currentNode = currentNode._parent;
            }

            return tempList;

        }

        public List<UnitDirection> GetDirectionListToStartingNode()
        {

            List<UnitDirection> tempList = new List<UnitDirection>();
            PathNode currentNode = this;

            while (currentNode.Parent != null)
            {
                tempList.Add(currentNode._directionSpawnedFrom);
                currentNode = currentNode._parent;
            }

            return tempList;

        }

        public static UnitDirection GetOppositeDirection(UnitDirection direction)
        {

            if (direction == UnitDirection.Right)
                return UnitDirection.Left;
            else if (direction == UnitDirection.Left)
                return UnitDirection.Right;
            else if (direction == UnitDirection.Up)
                return UnitDirection.Down;
            else
                return UnitDirection.Up;

        }

        #endregion

    }

    enum NodePlaceResult
    {
        SucessfullyPlace,
        AlreadyPlacedHere,
        HitOtherPath
    }

    class PathFinder
    {

        #region Private Members

        MapPoint _pointA;
        MapPoint _pointB;

        Map _map;
        UnitLayer _layer;

        PathNode _currentPoint;

        PathNode[,] _nodeMapA;
        PathNode[,] _nodeMapB;

        PathNode[,] _switchMapA;
        PathNode[,] _switchMapB;

        #endregion

        #region Properties

        #endregion

        #region Constructors

        public PathFinder(Map map, UnitLayer layer)
        {

            _map = map;
            _layer = layer;

        }

        #endregion

        #region Methods

        public List<UnitDirection> FindPath(MapPoint pointA, MapPoint pointB)
        {

            // Save points for finder to use
            _pointA = pointA;
            _pointB = pointB;

            // If Point B isn't accessable now, don't even bother running through algorithms
            if (!_map.TileIsPassable(_layer, _pointB))
                return null;

            List<UnitDirection> returnList = null;

            // Try simple techniques that will work the majority of the time
            returnList = SimpleFind();
            if (returnList != null)
                return returnList;

            // Try a comprehensive search
            returnList = ComprehensiveFind();
            if (returnList != null)
                return returnList;

            // No Path exists..
            return null;

        }

        List<UnitDirection> SimpleFind()
        {

            List<UnitDirection> tempList = new List<UnitDirection>();

            _currentPoint = new PathNode(null,_pointA, UnitDirection.Left);

            // i is used to try 6 slightly different paths, determined by SimpleFindRound(int i)
            for (int i = 0; i < 6; ++i)
            {
                while (!_currentPoint.MapPoint.Equals(_pointB))
                {
                    // No difference in Y, just go left or right
                    if (_currentPoint.MapPoint.Y == _pointB.Y)
                    {
                        if (_currentPoint.MapPoint.X > _pointB.X)
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Left);
                        }
                        else
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Right);
                        }
                    }
                    // No difference in X, just go up or down
                    else if (_currentPoint.MapPoint.X == _pointB.X)
                    {
                        if (_currentPoint.MapPoint.Y > _pointB.Y)
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Up);
                        }
                        else
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Down);
                        }
                    }
                    // Use SimpleFindRound to determine if we should move vertically or horizontally
                    else if (SimpleFindRound(i))
                    {
                        if(_currentPoint.MapPoint.X > _pointB.X)
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Left);
                        }
                        else
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Right);
                        }
                    }
                    else
                    {
                        if (_currentPoint.MapPoint.Y > _pointB.Y)
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Up);
                        }
                        else
                        {
                            _currentPoint = _currentPoint.SpawnChild(UnitDirection.Down);
                        }
                    }


                    try
                    {
                        if (!_map.TileIsPassable(_layer, _currentPoint.MapPoint))
                        {
                            // Hit something... This way doesn't work
                            _currentPoint = null;
                            break;
                        }
                    }
                    catch
                    {
                        break;
                    }

                }

                if (_currentPoint != null)
                    break;
                else if (i != 5)
                    _currentPoint = new PathNode(null, _pointA, UnitDirection.Left);

            }

            if (_currentPoint == null)
                return null;
            else
                return _currentPoint.GetDirectionListFromEndingNode();

        }

        bool SimpleFindRound(int i)
        {
            switch (i)
            {
                case 0:
                    return (Math.Abs(_currentPoint.MapPoint.X - _pointB.X) > Math.Abs(_currentPoint.MapPoint.Y - _pointB.Y));
                case 1:
                    return (Math.Abs(_currentPoint.MapPoint.X - _pointB.X) >= Math.Abs(_currentPoint.MapPoint.Y - _pointB.Y));
                case 2:
                    return (Math.Abs(_currentPoint.MapPoint.X - _pointB.X) < Math.Abs(_currentPoint.MapPoint.Y - _pointB.Y));
                case 3:
                    return (Math.Abs(_currentPoint.MapPoint.X - _pointB.X) <= Math.Abs(_currentPoint.MapPoint.Y - _pointB.Y));
                case 4:
                    return false;
                case 5:
                    return true;
                default:
                    throw new Exception("Error in SimpleFindRound, round invalid: " + i.ToString());
            }
        }

        List<UnitDirection> ComprehensiveFind()
        {

            _nodeMapA = new PathNode[_map.WidthInTiles, _map.HeightInTiles];
            _nodeMapB = new PathNode[_map.WidthInTiles, _map.HeightInTiles];

            PathNode theMatch = null; 

            Queue<PathNode> _pointABreadth = new Queue<PathNode>();
            Queue<PathNode> _pointBBreadth = new Queue<PathNode>();

            _pointABreadth.Enqueue(new PathNode(null, _pointA, UnitDirection.Left));
            _pointBBreadth.Enqueue(new PathNode(null, _pointB, UnitDirection.Left));

            while (true)
            {

                // Expand from Point A
                if(_pointABreadth.Count > 0)
                {
                    _switchMapA = _nodeMapA;
                    _switchMapB = _nodeMapB;
                    theMatch = ExpandAndCheck(_pointABreadth);
                    if (theMatch != null || _pointABreadth.Count == 0)
                        break;
                }
                else
                {
                    // Ran out of nodes to check, no possible path
                    return null;
                }

                // Expand from Point B
                if(_pointBBreadth.Count > 0)
                {
                    _switchMapB = _nodeMapA;
                    _switchMapA = _nodeMapB;
                    theMatch = ExpandAndCheck(_pointBBreadth);
                    if (theMatch != null || _pointBBreadth.Count == 0)
                        break;
                }
                else
                {
                    // Ran out of nodes to check, no possible path
                    return null;
                }

            }

            if (theMatch == null)
            {
                return null;
            }
            else
            {

                // Connect two paths

                List<UnitDirection> ret = theMatch.GetDirectionListFromEndingNode();
                ret.AddRange(theMatch.Children[0].GetDirectionListToStartingNode());

                if (_switchMapA == _nodeMapB)
                    return FlipAndReverse(ret);
                else
                    return ret;



            }

        }

        PathNode ExpandAndCheck(Queue<PathNode> pointBreadth)
        {

            PathNode nextNode = pointBreadth.Dequeue();
            PathNode tempNode = null;

            tempNode = ExpandAndCheck(nextNode, pointBreadth, UnitDirection.Left);
            if (tempNode != null)
                return tempNode;

            tempNode = ExpandAndCheck(nextNode, pointBreadth, UnitDirection.Right);
            if (tempNode != null)
                return tempNode;

            tempNode = ExpandAndCheck(nextNode, pointBreadth, UnitDirection.Up);
            if (tempNode != null)
                return tempNode;

            tempNode = ExpandAndCheck(nextNode, pointBreadth, UnitDirection.Down);
            if (tempNode != null)
                return tempNode;

            return null;

        }

        PathNode ExpandAndCheck(PathNode node, Queue<PathNode> pointBreadth, UnitDirection direction)
        {
            
            PathNode tempSpawn = null;

            // Expand and check Left
            if (CanExpand(node, direction))
            {
                tempSpawn = node.SpawnChild(direction);
                NodePlaceResult result = PlaceNodeOnMap(tempSpawn);
                if (result == NodePlaceResult.SucessfullyPlace)
                {
                    pointBreadth.Enqueue(tempSpawn);
                    return null;
                }
                else if (result == NodePlaceResult.HitOtherPath)
                {
                    return tempSpawn;
                }
                else
                {
                    return null;
                }
            }
            else
            {
                return null;
            }

        }

        NodePlaceResult PlaceNodeOnMap(PathNode node)
        {
            if (_switchMapB[node.MapPoint.X, node.MapPoint.Y] == null)
            {
                if (_switchMapA[node.MapPoint.X, node.MapPoint.Y] == null)
                {
                    _switchMapB[node.MapPoint.X, node.MapPoint.Y] = node;
                    return NodePlaceResult.SucessfullyPlace;
                }
                else
                {
                    node.AddChild(_switchMapA[node.MapPoint.X, node.MapPoint.Y]);
                    return  NodePlaceResult.HitOtherPath;
                }
            }
            else
            {
                return  NodePlaceResult.AlreadyPlacedHere;
            }
        }

        bool CanExpand(PathNode node, UnitDirection direction)
        {

            if (direction == UnitDirection.Down)
                return _map.TileIsPassable(_layer, new MapPoint(node.MapPoint.X, node.MapPoint.Y + 1));
            else if (direction == UnitDirection.Up)
                return _map.TileIsPassable(_layer, new MapPoint(node.MapPoint.X, node.MapPoint.Y - 1));
            else if (direction == UnitDirection.Left)
                return _map.TileIsPassable(_layer, new MapPoint(node.MapPoint.X - 1, node.MapPoint.Y));
            else
                return _map.TileIsPassable(_layer, new MapPoint(node.MapPoint.X + 1, node.MapPoint.Y));
                
        }

        List<UnitDirection> FlipAndReverse(List<UnitDirection> first)
        {
            List<UnitDirection> second = new List<UnitDirection>();

            while (first.Count > 0)
            {
                second.Add(PathNode.GetOppositeDirection(first.Last()));
                first.RemoveAt(first.Count - 1);
            }

            return second;

        }

        #endregion

    }
}
